package demo20;

import java.util.Arrays;

public class dui {
    public int elem[];
    public int useSized;
    public dui(){
        this.elem=new int[10];
    }
    //初始化
    public void initial(int[] array){
        for(int i=0;i< array.length;i++){
          this.elem[i]=array[i];
            this.useSized++;
        }
        create();
    }
    //创建
    public void create(){

        for(int p=(useSized-1)/2;p>=0;p--){
            shiftdown(p);
        }
        display();
    }
    public void shiftdown(int p){
        int child=2*p+1;
        while(child<useSized){
            if(child+1<useSized&&elem[child]>elem[child+1]){
                child++;
            }
            if(elem[child]<elem[p]){
                swap(elem,child,p);
                p=child;
                child=2*p+1;

            }else {
                break;
            }
        }
    }
    public void swap(int[]elem,int child,int p){
        int temp=elem[child];
        elem[child]=elem[p];
        elem[p]=temp;
    }
    public void insert(int num){
        if(full()){
            elem= Arrays.copyOf(elem,2*elem.length);
        }
        useSized++;//不能与下面两步交换顺序，交换后由于useSize为全局变量++后都改变，
        elem[useSized-1]=num;
        shiftup(useSized-1);

    }
    public void shiftup(int child){
        int parent=(child-1)/2;
        while(child>0){
            if (elem[parent]>elem[child]) {
                swap(elem, child, parent);
                child = parent;
                parent = (child - 1) / 2;
            }else{
                break;
            }

        }
        display();
    }
    public boolean empty(){
        return useSized==0;
    }
    public void display(){
        System.out.println();
        System.out.println("小根堆为:");
        for(int i=0;i<useSized;i++){
            System.out.print(elem[i]+" ");
        }
        System.out.println();
    }
    public boolean full(){
        if(useSized==elem.length){
            System.out.println("堆已满！");
            return false;
        }else{
            return true;
        }
    }
    public void peek(){
        if(empty()){
            System.out.println("堆空！");
            return;
        }
        System.out.println();
        System.out.println("堆顶元素为：");
        System.out.println(elem[0]+" ");
        System.out.println();
    }
    public void poll(){
        if(empty()){
            System.out.println("堆空！");
            return;
        }
        System.out.println();
        System.out.println("获取堆顶元素为：");
        System.out.println(elem[0]+" ");
        int temp=elem[0];
        elem[0]=elem[useSized-1];
        elem[useSized-1]=temp;
        useSized--;
        shiftdown(0);

    }
    //删除
    public void delete(int num2){
        for(int i=0;i<useSized;i++){
            if(elem[i]==num2){
                elem[i]=elem[useSized-1];
                useSized--;
                int k=i;
                shiftdown(k);
                display();
                return;
            }
        }
        System.out.println("堆中没有这个数！");
        System.out.println();
    }
}
